关于这道题，我实在想不通为何被列入了 Medium 的行列，插入排序是知乎上有名的梗，如果这个算法不能在十分钟内流畅的写出来，应该万般羞愧的躲进活死人墓，苦练各种基本功。
简单过一下插入排序的过程吧：
[3 7] 4 9 5 2 6 1
^ ^
[3 4 7 9] 5 2 6 1
^ ^
[3 4 5 7 9] 2 6 1
^ ^
[2 3 4 5 7 9] 6 1
^ ^
[2 3 4 5 6 7 9] 1
^ ^
[1 2 3 4 5 6 7 9]从上述过程中，可以看出，每一次遇到逆序情况(即 7->4, 9->5, 9->2, 9->6, 9->1 等情况)时，都需要从头开始比对，遇到合适的位置，便将当前元素插过去。所以算法的核心是：
1->3->4->2->5 => 1->2->3->4->5
^ ^
i p pNode的过程如何实现。假设当前指针为 p，要插入的节点指针 pNode，从头检测的指针为 i, 则有：
ListNode *pNode = p->next;
p->next = pNode->next;
pNode->next = i->next;
i->next = pNode;如果看不太明白，还需要动手在纸上画一画，链表题如果不动手，的确是很难理清楚的。
#include <cstddef>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
ListNode pre_head(0);
pre_head.next = head;
for (ListNode *p = head; p; )
if (p->next && p->val > p->next->val) {
ListNode *i = &pre_head;
while (!(i->next->val > p->next->val))
i = i->next;
ListNode *pNode = p->next;
p->next = pNode->next;
pNode->next = i->next;
i->next = pNode;
} else { p = p->next; }
return pre_head.next;
}
};